package class01;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/binary-search/">704. 二分查找</a>
 */
public class Code04_BSExist {
    // L...R 至少一个数的边界条件
    public static boolean binary1(int[] arr, int number) {
        int L = 0, R = arr.length - 1;
        while (L <= R) {  // 至少一个数的时候
            int M = L + ((R - L) >> 1);  // 范围缩小一半，防溢出写法
            if (number < arr[M]) {
                R = M - 1;
            } else if (number > arr[M]) {
                L = M + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    // L...R 至少剩下两个数的边界条件
    public static boolean binary2(int[] arr, int number) {
        int L = 0, R = arr.length - 1;
        while (L < R) {  // 至少两个数的时候
            int M = L + ((R - L) >> 1);
            if (number < arr[M]) {
                R = M - 1;
            } else if (number > arr[M]) {
                L = M + 1;
            } else {
                return true;
            }
        }
        return arr[L] == number;  // 退出循环的时候，还有一个数没有确定
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = (int) (Math.random() * (10 - 1) + 1);
        }
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(binary1(arr, 2));
        System.out.println(binary2(arr, 2));
    }
}
